Error detection and correction codes have been in use in electronic systems to reduce the probability of errors being introduced into data being stored or communicated in the face of physical and electrical phenomena that introduce errors into the data. For example, FIG. 1 shows a typical conceptualization of a communication system. The underlying model of the communication system is that a serial data stream needs to be sent from the source 101 to the destination 109. The source data is first passed through a source encoder 102 that compresses the original serial source data stream X by removing any redundancy in it. The channel encoder 103 adds redundancy in a controlled and systematic fashion in order to facilitate detecting any errors introduced between the channel encoder 103 and the channel decoder 107, possibly with the option of correcting those errors as well. The errors are generally assumed to be introduced by an imperfect channel 105 which, due to noise or other physical or electrical phenomena, cause the symbol stream r′ coming out of the channel 105 to be different from the symbol stream v′ going into the channel 105. It is the channel encoder 103, then, that typically introduces the error correction code (ECC) into the data stream.
The channel modulator 104 has the purpose of translating the incoming bit stream v into the electrical signals of the channel 105. In the case of a binary digital channel, the modulator is straightforward—it typically passes the encoded data stream v directly and unchanged to the channel such that v′=v. However, there are channels that communicate symbols one at a time, selected from a symbol set that has more than two elements. For example, if a communications channel is able to send one of four voltages during each data transmission time period, then the size of the symbol set is 4. In general, the transmitted symbols v′[j] are selected from the set of symbols S={s0, s1, s2, . . . sl}, where the size of the symbol set is l. Those skilled in the art would understand that there are many such channels, particularly, for example, those using phase-shift keying (PSK) amplitude modulation, and multi-bit-per-cell Flash or DRAM memories. In these cases, the channel modulator 104 takes two bits of the input stream v to choose one symbol of symbol stream v′. In the case of a binary digital channel, the symbols that make up symbol stream v′, whether they are represented by currents, voltages, charges, or some other quantity, are easily associated with the binary digits 0 and 1. For binary channels, the size of the symbol set l=∥S∥ is 2. In light of this association, and as indicated above, in this case, typically v′ can be viewed as being the same as v, though other relationships are possible. One common alternative is, for example, for v′ to equal the complement of v.
Regardless of the size of the symbol set S, the noise or otherwise induced errors introduced in the channel would change one communicated or stored symbol into another, as will be discussed later.
The role of the channel demodulator 106 is to convert the received symbol stream r′ into a binary received encoded data stream r. Depending on what errors were introduced into the symbol stream by the channel, the received encoded data stream r is a close but not exact replica of the encoded data stream v, though probably, but not necessarily, shifted in time. The amount of time shift depends on whether the channel is a communications channel, in which case, the time delay is equal to the propagation delay through the modulator 104, the channel 105, and the demodulator 106. In the case that the channel is a memory device, the time shift between v and r can be substantial, particularly in the cases in which the symbol stream v′ is embedded into the memory when the memory is manufactured (such as, for example, CDs and DVDs).
The role of the channel decoder 107 is to remove the redundancy introduced by channel encoder 103 in order to produce the corrected data stream w. If the error correction code is well designed with the channel's characteristics in mind, then the errors introduced into the received symbol stream r′ are removed so that there is a very high probability that each and every bit in decoded data stream w is identical to the corresponding bit in the compressed data stream u. Some error correction codes are able to detect some classes of errors that they are unable to correct. When these codes are used, then occasionally, in the presence of a detectable but uncorrectable error in the received symbol stream, the corrected data stream is known to be erroneous and this knowledge is generally communicated to a control mechanism to prevent the erroneous corrected data from being used until the information can be regenerated and/or resent.
The final phase of the process is the source decoder 108, which undoes the data compression performed on the data stream by the source encoder 102 to produce a final received data stream x′ that is ideally identical to the source data stream x. However, many communications and memory systems do not include a source encoder/source decoder pair. Under such circumstances, the input to the channel encoder 103 would be the raw source data stream, and the output of the channel decoder 107 would be the final received data stream x′ that is sent to the data's destination 109.
FIG. 2 shows a simplified view of a communications or storage system, one in which there is no source encoder or source decoder, and in which the channel is a binary digital channel so that the transmitted symbols are the same as the encoded data stream bits. The channel moderator and demodulators are therefore effectively pass-through devices without significance to the overall system. The result is that the only blocks of significance are the channel encoder 202 and the channel decoder 204. In this figure the channel 203 is represented by a binary addition, which is functionally equivalent to a single exclusive OR gate. In this conceptualization of the channel and the errors, the error stream e is a binary bit stream of equal length to the encoded data stream v. A one in the error stream means an error is injected into the data stream by the channel at that bit position. The nature of the binary addition function is that the presence of an error changes a zero in the data stream to a one and vice versa. In this conceptualization of the channel, the errors are independent of the data in that a one in the error stream causes an error regardless of whether the data bit in the corresponding position in the encoded data stream is a zero or a one. In addition, the probability of an error being introduced is considered to be constant from one symbol to the next. This type of channel is referred to as a Binary Symmetric Channel (BSC). There are other channel models which include the concept that the probability of an error in one bit position is related to the probability that an error occurred in the previous bit position. These channels are the to have memory and they experience bursts of closely spaced errors.
FIG. 3 shows another simplification of the general communications system of FIG. 1, in this case with the names of the terms changed to reflect a storage application. In these applications, the communications channel is replaced by a memory device 303. The memory device can be a physically static devices such as, for example, one or more CDs or DVDs, active devices such as semiconductor memories, such as, for example, dynamic random access memories (DRAMs), Flash memories, or Read Only Memories (ROMs); or any other manner of device whose function is in part to store information for a period of time. In this conceptualization, the channel encoder is called an ECC encoder 302. The encoded data stream is written into the memory device either once at manufacture, once in the field, or repeatedly as the device is being used. The received data stream r is generally retrieved from the memory devices via read operations of one type or another depending on the specifics of the memory device. In the case of a random access memory device, the data need not be retrieved in the order written, and the association between written symbols and read symbols is by implicitly or explicitly provided address. It will be understood that the ECC Decoder can reside without limitation within the memory controller or within the memory device integrated circuit or anywhere in between as a discrete device or between the memory controller and the data destination.
Memory devices typically store information in memory cells. The majority of memory types store a single bit of information in each memory cell. For these devices, the symbol set is the set of binary digits zero and one and there is no corresponding channel modulator. The exception is that in many semiconductor memory types there is an inversion that exists along the signal path that carries the encoded data bits v[i] to the memory cells so that the stored symbols are in some way inverted from the encoded data bits for some or all of the storage cells.
There also exist memory devices, both commercially available and proposed in the literature of the art, which store symbols from a larger symbol set in each memory location. For example, many multi-level Flash memory devices program each memory cell to one of four levels, thereby storing two bits worth of the encoded data stream into each memory location. For these devices, the equivalent of the channel modulator and channel demodulator—the circuitry or algorithm that manages the mapping between encoded data bits and stored symbols, as well as the corresponding mapping between the stored symbols and the bits read out received data stream r[i] is part of the memory controller, responsible from reading and possibly writing the memory device.
A person knowledgeable in the art will understand that error correction codes and channel modulation schemes are designed with the error characteristics of specific channels in mind and that there are a wide variety of code types to choose from for designing any particular memory or communication system. These error correction codes generally do not reduce the probability of error in the corrected data stream w to zero. Instead they merely reduce that probability substantially, to a level below some subjectively acceptable error rate.
FIG. 4 shows a probability transition diagram of a binary symmetric channel, as described in reference to FIG. 2 above. Binary symmetric channels pass the bits of the encoded data stream v[i] through the channel to the channel decoder as the bits of the received data stream r[i]. The probability in any bit position that an error is introduced, i.e. that r[i] is different from v[i], is p, and so the probability that the bit is passed through uncorrupted by the channel is 1-p. The channel is symmetric in that the probability of an error is the same regardless of whether the encoded data bit is a zero or a one.
Much of information and coding theory is built on the assumptions inherent in the binary symmetric channel model. But in reality, many communications channels and memory devices are either non-binary or not symmetric with respect to their error properties. In practice, many of the phenomena that cause an error to be injected into the received data stream r preferentially operate on the different symbols in the channel. For example, if the characteristics of a binary channel are such that one symbol is always passed error free, while the other symbol is changed to be the first with probability p, then the channel is referred to as a Z-channel. FIG. 5 shows the probability transition diagram for such a channel in which a zero is always passed unchanged, while a one is changed to a zero with probability p. Error probability transition diagrams in which not all errors are possible (such as in FIG. 5, in which an error from a 0 to a 1 is not possible or sufficiently improbable to be discounted from consideration) are called incomplete. Channels and memories with error injection mechanisms that only produce some types of error transitions but not others are similarly referred to as incomplete.
FIG. 6 shows the probability transition diagram for another incomplete channel. In this case, the channel is capable of sending one symbol at a time chosen from a symbol set consisting of three symbols. The physical or electrical properties used to convey these three symbols is not relevant to the abstract analysis of the error characteristics of the channel, so the symbols are simply labeled a, b and c. These symbols may be represented by different voltages, currents, charge, or phases among others. For example, symbol a might be represented by a positive voltage, symbol c by a negative voltage, and symbol b by a voltage close to ground. For this illustrative channel, symbol b is passed through the channel always unchanged, while symbols a and c are changed to symbol b with probability p and q, respectively. In this case, since this is a ternary channel, symbols input into the channel input are the items in the transmitted symbol stream v′ [j] and the symbols leaving the channel are the items in the received symbol stream r′ [j]. A channel that is characterized by a probability transition diagram like that shown in FIG. 6, in that the symbol set size is more than two and at least one possible error transition has a probability that is effectively zero, is called a non-binary incomplete channel. This channel is also asymmetrical in that not all conceivable errors have the same probability of occurring.
The ability to detect and correct errors in a transmitted signal can be characterized in terms of the Hamming distance of the code that is used. The Hamming distance between any two code words (sometimes called the “distance”) is the number of symbol positions in which the two code words are different. For example, the two binary code words 0011010 and 0010110 have Hamming distance 2 because they differ in two places. Similarly, the code words abacdda and acdadda have Hamming distance three in that they differ in three symbol positions. It is well understood that for a code for use on a complete channel (all errors between every pair of symbols in the symbol set are possible) to be able to correct t errors and detect t+1 errors, then the minimum separation of all code words has to be at least 2t+2. In particular the well recognized single error correcting, double error detecting (SECDED) binary Hamming codes have a minimum separation of 4 between all code words. All received words that are Hamming distance 1 from a code word are assumed to have a single error in them and therefore all such received data words can be corrected to that code word by the receiver. Any received data word that has a Hamming distance of 2 from more than one code word is assumed to have two errors in it. Since the Hamming distance from the received code word to two distinct valid code words is identical, the receiver cannot unambiguously determine which of the two code words was sent by the channel modulator. Under this circumstance, two errors are detectable but not correctable.